<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    function combinationSum(candidates, target) {
      /**
       * 该题采用深度优先+剪枝的方法，它与上一题"组合总和Ⅰ"非常相似，但多加了一个
       * 条件：每个数字不再可以无限制重复被选取，只能使用一次；因此我们对上一个算法
       * 进行改进即可：
       * 1.将递归中跳转到下一个元素变为跳转到下一个不重复的元素
       *    recursion(targetValue,combineed,index+1) => 
       *    recursion(targetValue,combined,notRepeatingIndex);
       * 2.将递归中减去当前值，继续递归本次元素变为继续递归下一个元素
       *    recursion(diff,[...combined,candidates[index]],index) => 
       *    recursion(diff,[...combined,candidates[index],index+1])
       */

      // 对数组进行排序，方便后续去重、剪枝处理
      candidates.sort((a, b) => a - b);
      // 定义输出数组
      let outArray = [];
      function recursion(targetValue, combined, index) {
        // 如果targetValue等于零，证明当前组合的和
        // 为target，将当前组合(combined)加入输出数组
        if (targetValue === 0) {
          outArray.push(combined);
          return;
        }
        // 如果当前索引超出了给定数组范围，直接return
        if (index >= candidates.length) return;
        // 初始化与当前元素不重复的后一个元素的索引为当前元素+1
        let notRepeatingIndex = index + 1;
        // 找到与当前元素不重复的后一个元素的索引，由于candidates
        // 为升序，因此仅需要找到与当前元素不同的元素，即可跳过全部
        // 相同的元素
        while (candidates[notRepeatingIndex] == candidates[index]) notRepeatingIndex++;
        // 如果当前目标值减去差值小于0，由于candidates为升序
        // 因此后续元素与当前差值依旧会小于0，因此舍去(剪枝)
        // 如果大于等于0则继续递归
        let diff = targetValue - candidates[index];
        if (diff >= 0) {
          // 跳到不重复的元素继续递归
          recursion(targetValue, combined, notRepeatingIndex);
          // 减去当前值，继续递归下一个元素
          recursion(diff, [...combined, candidates[index]], index + 1);
        }
      }
      // 执行递归
      recursion(target, [], 0)
      // 输出结果
      return outArray;
    }
    console.log(combinationSum(candidates = [10, 1, 2, 7, 6, 1, 5], target = 8))
  </script>
</body>

</html>